using System;
using System.Collections;
using System.Collections.Generic;

namespace ClearSpringNet.Util
{
    public class DoublyLinkedList<T> : IEnumerable<T>
    {
        private int _size;
        public ListNode2<T> Tail;
        public ListNode2<T> Head;

        public ListNode2<T> Add(T value)
        {
            var node = new ListNode2<T>(value);
            if (_size++ == 0)
            {
                Tail = node;
            }
            else
            {
                node.prev = Head;
                Head.next = node;
            }
            Head = node;
            return node;
        }

        public ListNode2<T> Enqueue(T value)
        {
            var node = new ListNode2<T>(value);
            if (_size++ == 0)
            {
                Head = node;
            }
            else
            {
                node.next = Tail;
                Tail.prev = node;
            }
            Tail = node;
            return node;
        }

        public ListNode2<T> AddAfter(ListNode2<T> node, T value)
        {
            var newNode = new ListNode2<T>(value);
            AddAfter(node, newNode);
            return newNode;
        }

        public void AddAfter(ListNode2<T> node, ListNode2<T> newNode)
        {
            newNode.next = node.next;
            newNode.prev = node;
            node.next = newNode;
            if (newNode.next == null)
            {
                Head = newNode;
            }
            else
            {
                newNode.next.prev = newNode;
            }
            _size++;
        }

        public void Remove(ListNode2<T> node)
        {
            if (node == Tail)
            {
                Tail = node.next;
            }
            else
            {
                node.prev.next = node.next;
            }

            if (node == Head)
            {
                Head = node.prev;
            }
            else
            {
                node.next.prev = node.prev;
            }
            _size--;
        }

        public int Size()
        {
            return _size;
        }

        public void Add(ListNode2<T> node)
        {
            node.prev = Head;
            node.next = null;

            if (_size++ == 0)
            {
                Tail = node;
            }
            else
            {
                Head.next = node;
            }

            Head = node;
        }

        public IEnumerator<T> GetEnumerator()
        {
            return GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public T first()
        {
            return Tail == null ? default(T) : Tail.getValue();
        }

        public T last()
        {
            return Head == null ? default(T) : Head.getValue();
        }

        public ListNode2<T> gethead()
        {
            return Head;
        }

        public ListNode2<T> tail()
        {
            return Tail;
        }

        public bool isEmpty()
        {
            return _size == 0;
        }

        public T[] toArray()
        {
            var i = 0;

            T[] a = new T[_size];
            foreach (var v in this)
            {
                a[i++] = v;
            }
            return a;
        }
    }

    class DoublyLinkedListIterator<T> : IEnumerable<T>
    {
        protected DoublyLinkedList<T> list;
        protected ListNode2<T> itr;
        protected int length;

        public DoublyLinkedListIterator(DoublyLinkedList<T> list)
        {
            length = list.Size();
            this.list = list;
            itr = list.Tail;
        }

        public bool hasNext()
        {
            return itr != null;
        }

        public T next()
        {
            var next = default(T);

            if (length != list.Size())
                next = itr.value;

            itr = itr.next;
            return next;
        }

        public void remove()
        {
            throw new NotImplementedException();
        }

        public IEnumerator<T> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }
}